#include "bintree.h"

int main(void)
{
	int op;
	struct bintree testtree = {0};
	struct binnode *p;
	
	show_menu();
	scanf("%d", &op);

	while (op != 0)
	{
		switch (op)
		{
		case 1:	
			createATree(&testtree);
			printf("treesize = %d\n", testtree.size);
			break;
		
		case 2:
			// preorderTraverse(&testtree, testtree.root, show_binnode_data);
			// printf("\n");
			// preorderTraverse1(&testtree, testtree.root, show_binnode_data);
			// printf("\n");
			preorderTraverse2(&testtree, testtree.root, show_binnode_data);

			break;
		case 3:
			// inorderTraverse(&testtree, testtree.root, show_binnode_data);
			// printf("\n");
			inorderTraverse1(&testtree, testtree.root, show_binnode_data);
			printf("\n");
			p = testtree.root->lchild->lchild;
			show_binnode_data(&testtree, p);
			while ((p = binnodeSucc(p)) != NULL)
			{
				show_binnode_data(&testtree, p);
			}
			
			break;
		case 4:
			// postorderTraverse(&testtree, testtree.root, show_binnode_data);
			// printf("\n");
			postorderTraverse1(&testtree, testtree.root, show_binnode_data);
			
			break;
		case 5:
			levelTraverse(&testtree, testtree.root, show_binnode_data);
			printf("\n");
			break;
		case 6:
			saveBintreeToFile(&testtree, testtree.root);
			break;
		case 7:
			loadBintreeFromFile(&testtree);
			break;
		case 8:
			destroyBintree(&testtree);
			break;
		default: break;
		}
		show_menu();
		scanf("%d", &op);
	}


	return 0;
}

/* 
 * 输入参数：tree二叉树 pdata指向需要插入的具体信息 parent指向以哪个结点作为父结点
 * 返回值： 新插入的结点指针
 * 功能： 新建结点，设置pdata指向的具体信息 并指向父结点parent 
*/
struct binnode * createBinnode(struct bintree *tree, void *pdata, struct binnode *parent)
{
	struct binnode *p;

	if ((p = (struct binnode *)malloc(sizeof(struct binnode))) == NULL)
	{
		exit(OVERFLOW);
	}
	memset(p, 0, sizeof(struct binnode));

	if ((p->pdata = malloc(tree->elemsize)) == NULL)
	{
		exit(OVERFLOW);
	}
	memset(p->pdata, 0, tree->elemsize);
	
	p->parent = parent;
	memcpy(p->pdata, pdata, tree->elemsize);

	return p;
}

/* 
 * 输入参数：tree二叉树 pdata指向需要插入的具体信息 parent指向以哪个结点作为父结点
 * 返回值： 新插入的结点指针
 * 功能： 新建结点，设置pdata指向的具体信息 并指向父结点parent 
 * 父结点左孩子指向新建结点 tree的size增加1 
 * 更新所有可能变化了高度的结点的height
*/
struct binnode * insertAsLeftChild(struct bintree *tree, void *pdata, struct binnode *parent)
{
	parent->lchild = createBinnode(tree, pdata, parent);

	++tree->size;	
	updateHeightAbove(parent);

	return parent->lchild;
}

/* 
 * 输入参数：tree二叉树 pdata指向需要插入的具体信息 parent指向以哪个结点作为父结点
 * 返回值： 新插入的结点指针
 * 功能： 新建结点，设置pdata指向的具体信息 并指向父结点parent 
 * 父结点右孩子指向新建结点 tree的size增加1 
 * 更新所有可能变化了高度的结点的height
*/
struct binnode * insertAsRightChild(struct bintree *tree, void *pdata, struct binnode *parent)
{
	parent->rchild = createBinnode(tree, pdata, parent);

	++tree->size;	
	updateHeightAbove(parent);

	return parent->rchild;
}
struct binnode * attachAsLeftChildren(struct bintree *tree, struct binnode * p, struct bintree *subtree)
{
	return NULL;
}
struct binnode * attachAsRightChildren(struct bintree *tree, struct binnode * p, struct bintree *subtree)
{
	return NULL;

}
/* 
 * 输入参数： 数中的某个结点
 * 返回值： 该结点规模（以该结点为根的子树中结点数量）
*/
int binnodeSize(struct binnode *p)
{
	int s = 1;	//本身为1个结点
	if (p->lchild != NULL)
	{
		s += binnodeSize(p->lchild);
	}
	if (p->rchild != NULL)
	{
		s += binnodeSize(p->rchild);
	}
	return s;
}

/* 
 * 输入参数： 数中的某个结点
 * 返回值： 该结点在中序遍历情况下的直接后继
*/
struct binnode * binnodeSucc(struct binnode *p)
{
	if (p->rchild != NULL)
	{
		p = p->rchild;
		while (p->lchild != NULL)
			p = p->lchild;
		return p;
	}
	else if (p->parent != NULL && p->parent->lchild == p)
	{
		return p->parent;
	}
	else if (p->parent != NULL && p->parent->rchild == p)
	{
		p = p->parent;
		while (p != NULL && p->parent != NULL)
		{
			if (p->parent->lchild == p)
				return p->parent;
			p = p->parent;
		}
		return NULL;
	}
	else
		return NULL;
}

//更新结点p的高度 返回值是更新后的该结点高度
int updateHeight(struct binnode *p)
{
	return p->height = 1 + maxOfTwoInt((p->lchild ? p->lchild->height : -1), (p->rchild ? p->rchild->height : -1));
}
int maxOfTwoInt(int a, int b)
{
	return a > b ? a : b;
}

//更新结点p及其所有父结点的高度
void updateHeightAbove(struct binnode * p)
{
	int lastheight;
	while (p != NULL)
	{
		lastheight = p->height;

		updateHeight(p);

		if (lastheight == p->height)
			return;
		else
			p = p->parent;
	}
}

void createATree(struct bintree *tree)
{
	struct binnode *p;

	char *a;
	char *b;
	char *c;
	char *d;
	char *e;
	char *f;
	char *g;

	tree->elemsize = sizeof(char);

	if ((a = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((b = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((c = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((d = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((e = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((f = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);
	if ((g = (char *)malloc(sizeof(char))) == NULL)
		exit(-1);

	*a = 'A';
	*b = 'B';
	*c = 'C';
	*d = 'D';
	*e = 'E';
	*f = 'F';
	*g = 'G';


	if ((tree->root = (struct binnode *)malloc(sizeof(struct binnode))) == NULL)
		exit(-1);
	memset(tree->root, 0, sizeof(struct binnode));
	tree->root->height = 1;
	tree->root->pdata = a;

	tree->size = 1;

	p = insertAsLeftChild(tree, (void *)b, tree->root);
	insertAsLeftChild(tree, (void *)d, p);
	p = insertAsRightChild(tree, (void *)e, p);
	insertAsLeftChild(tree, (void *)g, p);

	p = insertAsRightChild(tree, (void *)c, tree->root);
	insertAsRightChild(tree, (void *)f, p);



}

void show_menu(void)
{
	printf("0. exit\n");
	printf("1. create bintree\n");
	printf("2. preorderTraverse\n");
	printf("3. inorderTraverse\n");
	printf("4. postorderTraverse\n");
	printf("5. levelTraverse\n");
	printf("6. Save\n");
	printf("7. Load\n");
	printf("8. Destroy\n");


}
void show_binnode_data(struct bintree *pb, struct binnode *p)
{
	printf("%c\theight:%d\n", *((char *)p->pdata), p->height);
}

void preorderTraverse(struct bintree *pb, struct binnode *p, void visit())
{
	if (p == NULL)
		return;
	visit(pb, p);
	preorderTraverse(pb, p->lchild, visit);
	preorderTraverse(pb, p->rchild, visit);

}

void preorderTraverse1(struct bintree *pb, struct binnode *p, void visit())
{
	struct binnode *stack[STACKSIZE];
	struct binnode *x;
	int top = 0;

	if (p != NULL)
	{
		stack[++top] = p;
	}

	while (top)
	{
		x = stack[top--];
		visit(pb, x);

		if (x->rchild != NULL) stack[++top] = x->rchild;
		if (x->lchild != NULL) stack[++top] = x->lchild;
	}

}

void visitAlongLeftBranch(struct bintree *pb, struct binnode **pp, void visit(), struct binnode *stack[], int *top)
{
	struct binnode *p = *pp;
	while(p != NULL)
	{
		visit(pb, p);
		stack[++(*top)] = p->rchild;
		p = p->lchild;
	}
}
void preorderTraverse2(struct bintree *pb, struct binnode *p, void visit())
{
	struct binnode *x = p;
	struct binnode *stack[STACKSIZE];
	int top = 0;
	while (1)
	{
		visitAlongLeftBranch(pb, &x, visit, stack, &top);
		if (top == 0) break;
		x = stack[top--];
	}
}

void inorderTraverse(struct bintree *pb, struct binnode *p, void visit())
{
	if (p == NULL)
		return;
	inorderTraverse(pb, p->lchild, visit);
	visit(pb, p);	
	inorderTraverse(pb, p->rchild, visit);
}
void goAlongLeftBranch(struct bintree *pb, struct binnode *p, void visit(), struct binnode *stack[], int *top)
{
	while (p != NULL)
	{
		stack[++(*top)] = p;
		p = p->lchild;
	}
}
void inorderTraverse1(struct bintree *pb, struct binnode *p, void visit())
{
	struct binnode *stack[STACKSIZE];
	int top = 0;

	while (1)
	{
		goAlongLeftBranch(pb, p, visit, stack, &top);
		if (top == 0) break;
		p = stack[top--];
		visit(pb, p);
		p = p->rchild;
	}
}

void postorderTraverse(struct bintree *pb, struct binnode *p, void visit())
{
	if (p == NULL) return;

	postorderTraverse(pb, p->lchild, visit);
	postorderTraverse(pb, p->rchild, visit);
	visit(pb, p);

}
void gotoHLVFL(struct bintree *pb, struct binnode *stack[], int *top)
{
	struct binnode *x;
	while ((x = stack[(*top)]) != NULL)
	{
		if (x->lchild != NULL)
		{
			if (x->rchild != NULL)
				stack[++(*top)] = x->rchild;
			stack[++(*top)] = x->lchild;
		}
		else
		{
			stack[++(*top)] = x->rchild;
		}

		
	}
	--(*top);
}
void postorderTraverse1(struct bintree *pb, struct binnode *p, void visit())
{
	struct binnode *stack[STACKSIZE];
	int top = 0;

	if (p) stack[++top] = p;

	while (top != 0)
	{
		if (stack[top] != p->parent)
			gotoHLVFL(pb, stack, &top);
		p = stack[top--];
		visit(pb, p);
	}
}

void levelTraverse(struct bintree *pb, struct binnode *p, void visit())
{
	struct binnode *queue[STACKSIZE];
	int top = 0;
	int bottom = 0;

	queue[top++] = p;

	while (bottom != top)
	{
		p = queue[bottom++];
		visit(pb, p);
		if (p->lchild != NULL) queue[top++] = p->lchild;
		if (p->rchild != NULL) queue[top++] = p->rchild;
	}
}

FILE *save_to_file_pointer_pre;
FILE *save_to_file_pointer_in;
void saveOneNodePre(struct bintree *pb, struct binnode *p)
{
	fwrite(p->pdata, pb->elemsize, 1, save_to_file_pointer_pre);
}
void saveOneNodeIn(struct bintree *pb, struct binnode *p)
{
	fwrite(p->pdata, pb->elemsize, 1, save_to_file_pointer_in);
}
void saveBintreeToFile(struct bintree *pb, struct binnode *p)
{
	save_to_file_pointer_pre = fopen("preorder.dat", "wb");
	save_to_file_pointer_in = fopen("inorder.dat", "wb");

	fwrite(pb, sizeof(struct bintree), 1, save_to_file_pointer_pre);
	preorderTraverse2(pb, p, saveOneNodePre);
	inorderTraverse1(pb, p, saveOneNodeIn);

	fclose(save_to_file_pointer_pre);
	fclose(save_to_file_pointer_in);
}
void loadBintreeFromFile(struct bintree *ptree)
{
	FILE *fp_pre;
	FILE *fp_in;
	void *buffer;
	struct load_bintree_list prelist;
	struct load_bintree_list inlist;
	struct load_bintree_list *p;
	struct load_bintree_list *q;
	struct load_bintree_list *tail;

	destroyBintree(ptree);


	fp_pre = fopen("preorder.dat", "rb");
	fp_in = fopen("inorder.dat", "rb");

	fread(ptree, sizeof(struct bintree), 1, fp_pre);
	buffer = malloc(ptree->elemsize);
	
	p = &prelist;
	while (1)
	{
		fread(buffer, ptree->elemsize, 1, fp_pre);
		if (feof(fp_pre)) break;

		p->next = (struct load_bintree_list *)malloc(sizeof(struct load_bintree_list));
		p = p->next;
		p->next = NULL;
		p->pb = (struct binnode *)malloc(sizeof(struct binnode));
		p->pb->pdata = malloc(ptree->elemsize);
		memcpy(p->pb->pdata, buffer, ptree->elemsize);
	}

	for (p = prelist.next; p != NULL; p = p->next)
	{
		show_binnode_data(ptree, p->pb);
		p->pb->height = 0;
		p->pb->lchild = NULL;
		p->pb->rchild = NULL;
		p->pb->parent = NULL;
	}
	fclose(fp_pre);

	p = &inlist;
	while (1)
	{
		fread(buffer, ptree->elemsize, 1, fp_in);
		if (feof(fp_in)) break;

		p->next = (struct load_bintree_list *)malloc(sizeof(struct load_bintree_list));
		p = p->next;
		p->next = NULL;
		p->pb = (struct binnode *)malloc(sizeof(struct binnode));
		p->pb->pdata = malloc(ptree->elemsize);
		memcpy(p->pb->pdata, buffer, ptree->elemsize);
	}
	p->next = (struct load_bintree_list *)malloc(sizeof(struct load_bintree_list));
	p = p->next;
	p->next = NULL;
	tail = p;

	for (p = inlist.next; p->next != NULL; p = p->next)
	{
		show_binnode_data(ptree, p->pb);
		p->pb->height = 0;
		p->pb->lchild = NULL;
		p->pb->rchild = NULL;
		p->pb->parent = NULL;		
	}
	fclose(fp_in);

	for (q = inlist.next; q->next != NULL; q = q->next)
	{
		if (*(char *)q->pb->pdata == *(char *)prelist.next->pb->pdata)
			break;
	}
	ptree->root = q->pb;
	p = prelist.next;
	p = createBintreeFromInorderList(ptree, p, inlist.next, q, q->pb, -1);
	createBintreeFromInorderList(ptree, p, q->next, tail, q->pb, 1);


	free(buffer);
}
struct load_bintree_list * createBintreeFromInorderList(struct bintree *ptree, struct load_bintree_list * pre1, struct load_bintree_list *head, struct load_bintree_list *tail, struct binnode *parent, int left_right)
{
	struct load_bintree_list *q;
	static struct load_bintree_list *pre;
	pre = pre1;

	if (head == tail)
		return pre;

	pre = pre->next;
	for (q = head; q != tail; q = q->next)
	{
		if (*(char *)q->pb->pdata == *(char *)pre->pb->pdata)
			break;
	}
	if (left_right == -1)
	{
		parent->lchild = q->pb;
		q->pb->parent = parent;
		updateHeightAbove(parent);
	}
	else
	{
		parent->rchild = q->pb;
		q->pb->parent = parent;
		updateHeightAbove(parent);
	}
	pre = createBintreeFromInorderList(ptree, pre, head, q, q->pb, -1);
	createBintreeFromInorderList(ptree, pre, q->next, tail, q->pb, 1);
	return pre;
}

struct binnode *alllist233[NODESIZE];
int global_i;
void saveAllNode(struct bintree *pb, struct binnode *p)
{
	alllist233[global_i++] = p;
}
void destroyBintree(struct bintree *pt)
{
	int i;
	struct binnode *p;

	memset(alllist233, 0, sizeof(NODESIZE * sizeof(struct binnode *)));
	global_i = 0;
	preorderTraverse2(pt, pt->root, saveAllNode);

	for (i = 0; i < global_i; ++i)
	{
		p = alllist233[i];
		if (p->pdata) free(p->pdata);
		free(p);
	}

	pt->size = 0;
	pt->elemsize = 0;
	pt->root = NULL;
}